//输入一个字符串，打印出该字符串中字符的所有排列。 
//
// 
//
// 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 
//
// 
//
// 示例: 
//
// 输入：s = "abc"
//输出：["abc","acb","bac","bca","cab","cba"]
// 
//
// 
//
// 限制： 
//
// 1 <= s 的长度 <= 8 
// Related Topics 字符串 回溯 👍 487 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class ZiFuChuanDePaiLieLcof {
    public static void main(String[] args) {
        Solution solution = new ZiFuChuanDePaiLieLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 这一题需要避免重复访问并进行同层去重
         * 同层去重的话如果使用下标，一定要将元素进行排序
         * 由于本题目输入的是字符串，所以就使用的set进行的同层去重
         */
        List<String> res = new ArrayList<>();
        public String[] permutation(String s) {
            if ("".equals(s)) return new String[]{""};
            char[] chars = s.toCharArray();
            boolean[] visited = new boolean[chars.length];// 避免重复访问
            dfs(chars, visited, new StringBuilder());
            return res.toArray(new String[res.size()]);
        }
        private void dfs(char[] chars, boolean[] visited, StringBuilder path) {
            if (path.length() == chars.length) res.add(path.toString());
            else {
                // 需要进行同层去重以及同枝不重复访问
                Set<Character> set = new HashSet<>();// 同层去重
                for (int i = 0; i < chars.length; i++) {
                    if (visited[i] || set.contains(chars[i])) continue;
                    set.add(chars[i]);// 注意，这里不能回溯
                    path.append(chars[i]);
                    visited[i] = true;
                    dfs(chars, visited, path);
                    path.deleteCharAt(path.length() - 1);
                    visited[i] = false;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}